# Returns index of value in arr if present, else -1 
def binary_search(arr, lb, ub, value):

    # Limiting case, if lb(lower-bound) becomes higher than ub(upper-bound), return -1
    if lb>ub:
        return -1

    else:
        mid = (lb+ub) // 2
        # If value is at the middle index of the array 
        if arr[mid]==value:
            return mid

        # If value is less than the element at the middle index, then it can only be present at the left subarray
        elif value < arr[mid]:
            return binary_search(arr, lb, mid-1, value)

        # Else the value can only be present at the right subarray
        else:
            return binary_search(arr, mid+1, ub, value)

# Test array
arr = [ 3, 4, 9, 12, 16, 19, 25, 39, 54, 67, 71, 89, 101, 104, 113 ] 

# Taking the value input from user
value = int(input("Enter a value to be searched for in the array: "))

# Function call
result = binary_search(arr, 0, len(arr)-1, value)

# Displaying the output
if result == -1:
    print("Given value is not present in the array.")
else:
    print("Given value is present at index " + str(result) + ".")